using System;
using System.Collections.Generic;

namespace snacks{
    enum BType{None, Snake, Snack, Wall};
    class BInfo : IEquatable<BInfo>{
        public BType Type { get; set; }
        public ConsoleColor Color { get; set; }

        public BInfo(BType t = BType.None, ConsoleColor consoleColor = ConsoleColor.White) {
            Type = t;
            Color = consoleColor;
        }

        public virtual bool Equals(BInfo other)
        {
            return Type == other.Type && Color == other.Color;
        }
    };

    class BSnakeInfo : BInfo {
        public BSnakeInfo(ConsoleColor consoleColor = ConsoleColor.White) : base(BType.Snake, consoleColor){
        }
    }

    class BSnackInfo : BInfo
    {
        public int Value { get; set; }
        public BSnackInfo(ConsoleColor consoleColor = ConsoleColor.White, int val = 1) : base(BType.Snack, consoleColor)
        {
            Value = val;
        }

        public override bool Equals(BInfo other)
        {
            return other is BSnackInfo ? base.Equals(other) && Value == (other as BSnackInfo).Value : false;
        }
    }
    class Map{
        BInfo[,] mapData;
        public int[,] SnackDis;
        public int[,] ConSize;
        int N,M;

        public BInfo this[int x, int y]{
            get => mapData[x,y];
            set => mapData[x,y] = value;
        }

        public BInfo this[Vector pos] {
            get => mapData[pos.x, pos.y];
            set => mapData[pos.x, pos.y] = value;
        }

        public Map(int n, int m, bool hasWall = true) {//n for x, m for y
            N = n; M = m;
            mapData = new BInfo[n, m];
            SnackDis = new int[n ,m];
            ConSize = new int[n, m];

            for (int i = 0; i < n; ++i)
                for (int j = 0; j < m; ++j) {
                    mapData[i, j] = new BInfo();
                    SnackDis[i, j] = 0x3fffffff;
                }

            if (hasWall)
            {
                for (int i = 0; i < m; ++i)
                    mapData[0, i].Type = BType.Wall;
                for (int i = 0; i < m; ++i)
                    mapData[n - 1, i].Type = BType.Wall;
                for (int i = 1; i < n - 1; ++i)
                    mapData[i, 0].Type = BType.Wall;
                for (int i = 1; i < n - 1; ++i)
                    mapData[i, m - 1].Type = BType.Wall;
            }
        }

        public Map(int n, bool hasWall = true) : this(n, n, hasWall) { }

        public void Update(){
            CalSnackDis();
            CalConSize();
        }

        void CalSnackDis(){
            Queue<Vector> list = new Queue<Vector>();

            for(int i = 0; i < N; ++i)
                for(int j = 0; j < M; ++j) {
                    if(mapData[i, j].Type == BType.Snack) {
                        SnackDis[i, j] = 0;
                        list.Enqueue(new Vector(i, j));
                    } else SnackDis[i, j] = 0x3ffffff;
                }

            Vector v, t;
            while(list.Count != 0) {
                v = list.Dequeue();
                for(int i = 0; i < 4; ++i){
                    t = v + Int2Dir(i);
                    //Console.WriteLine("UPD " + Int2Dir(i) +" "+ v);
                    if(t.x >= 0 && t.y >= 0 && t.x < N && t.y < M && 
                    SnackDis[t.x, t.y] > SnackDis[v.x, v.y] + 1) {
                        SnackDis[t.x, t.y] = SnackDis[v.x, v.y] + 1;
                        list.Enqueue(t);
                    }
                }
            }
        }

        void CalConSize(){
            Queue<Vector> q = new Queue<Vector>();
            List<Vector> l = new List<Vector>();

            for(int i = 0; i < N; ++i)
                for(int j = 0; j < M; ++j) {
                    ConSize[i, j] = -1;
                }
            
            Vector t, c;
            for(int i = 0; i < N; ++i)
                for(int j = 0; j < M; ++j) {
                    if(ConSize[i, j] == -1 && (mapData[i, j].Type == BType.None ||
                    mapData[i, j].Type == BType.Snack)) {
                        ConSize[i, j] = 0;
                        t = new Vector(i, j);
                        q.Enqueue(t); l.Add(t);

                        while(q.Count != 0) {
                            t = q.Dequeue();
                            for(int k = 0; k < 4; ++k){
                                c = t + Int2Dir(k);
                                if(ConSize[c.x, c.y] == -1 && (mapData[c.x, c.y].Type == BType.None ||
                                mapData[c.x, c.y].Type == BType.Snack)) {
                                    ConSize[c.x, c.y] = 0;
                                    q.Enqueue(c); l.Add(c);
                                }
                            }
                        }

                        foreach(var v in l){
                            ConSize[v.x, v.y] = l.Count;
                        }

                        l.Clear();
                    }
                }
            // for(int i = 0; i < N; ++i){
            //     for(int j = 0; j < M; ++j) {
            //         Console.Write(ConSize[i, j]);
            //     }
            //     Console.WriteLine();
            // }
        }

        Vector Int2Dir(int i) {
            switch(i){
                default:
                case 0:
                    return new Vector(-1, 0);
                case 1:
                    return new Vector(1, 0);
                case 2:
                    return new Vector(0, -1);
                case 3:
                    return new Vector(0, 1);
            }
        }
    }
}